package com.demo.chapter13functionprogramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

//获取{1,4,9}的子集
public class ChildList {

	public static void main(String[] args) {
        List<List<Integer>> subs = subsets(Arrays.asList(1, 4, 9));
        subs.forEach(System.out::println);
        System.out.println("======================");
        List<List<Integer>> subs2 = subsets2(Arrays.asList(1, 4, 9));
        subs2.forEach(System.out::println);
    }

	//递归
    public static List<List<Integer>> subsets(List<Integer> l) {
    	l.forEach(System.out::println);
    	System.out.println("----------------");
        if (l.isEmpty()) {
            List<List<Integer>> ans = new ArrayList<>();
            ans.add(Collections.emptyList());
            return ans;
        }
        Integer first = l.get(0);
        List<Integer> rest = l.subList(1, l.size());

        List<List<Integer>> subans = subsets(rest);
        System.out.print("subans=");
        subans.forEach(System.out::println);

        List<List<Integer>> subans2 = insertAll(first, subans);
        System.out.print("subans2=");
        subans2.forEach(System.out::println);
    	System.out.println("----------------");

        return concat(subans, subans2);
    }

    //尾递归
    public static List<List<Integer>> subsets2(List<Integer> l) {
    	List<List<Integer>> acc = new ArrayList<>();
    	acc.add(Collections.emptyList());

    	Integer first = l.get(0);
        List<Integer> rest = l.subList(1, l.size());

        return factorial(acc, first, rest);
    }

    //acc：累加结果
    //first：第一个元素
    //rest：剩余元素
    public static List<List<Integer>> factorial(List<List<Integer>> acc, Integer _first, List<Integer> _rest){
    	if (_first == null) {
            return acc;
        }

    	List<List<Integer>> subans2 = insertAll(_first, acc);
    	Integer first;
    	List<Integer> rest;
    	if(_rest.isEmpty()){
    		first = null;
    		rest = null;
    	}else{
    		first = _rest.get(0);
    		rest = _rest.subList(1, _rest.size());
    	}

    	return factorial(concat(acc, subans2), first, rest);
    }

    public static List<List<Integer>> insertAll(Integer first, List<List<Integer>> lists) {
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> l : lists) {
            List<Integer> copyList = new ArrayList<>();
            copyList.add(first);
            copyList.addAll(l);
            result.add(copyList);
        }
        return result;
    }

    //concat是纯函数，虽然它内部对对象进行修改，向列表r添加元素，但是它返回的结果基于参数却没有修改任何一个传入的参数
    static List<List<Integer>> concat(List<List<Integer>> a, List<List<Integer>> b) {
        List<List<Integer>> r = new ArrayList<>(a);
        r.addAll(b);
        return r;
    }

}
